package com.topInterview;

public class leecode124 {
    public int maxProfit(int k, int[] arr) {
        if (arr == null || arr.length < 1) {
            return 0;
        }
        int N = arr.length;
        if (k >= N / 2) {
            return allTrans(arr);
        }
        //每个元素代表，0-i位置，参与小于k次的交易收益
        int[][] dp = new int[N][k + 1];

        for (int i = 1; i < N; i++) {
            for (int j = 1; j <= k; j++) {
                //p1,i位置不参与交易
                dp[i][j] = dp[i - 1][j];
                //i位置参与交易，并作为最后一次卖出时机
                for (int p = 0; p <= i; p++) {
                    //dp[i][j] = 在0~i-1位置上执行不超过j-1此交易，再加上arr[i]买入-0~i-1位置上的值，取最大
                    dp[i][j] = Math.max(dp[p][j - 1] + arr[i] - arr[p], dp[i][j]);
                }
            }
        }

        return dp[N - 1][k];

    }

    //参与所有交易
    public int allTrans(int[] arr) {

        int ans = 0;
        //每次买在股票上坡
        for (int i = 1; i < arr.length; i++) {
            ans += arr[i] - arr[i - 1] > 0 ? arr[i] - arr[i - 1] : 0;
        }
        return ans;
    }
}
